package LC;

/**
 * https://leetcode.com/problems/gas-station/description/
 * There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
 * You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1).
 * You begin the journey with an empty tank at one of the gas stations.
 * Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
 * Note:
 * The solution is guaranteed to be unique.
 */
public class LC_134_GasStation_DP_Greedy {
    public static void main(String[] args) {
        int start = Solution.canCompleteCircuit(new int[]{1, 2, 3}, new int[]{1, 2, 3});
        System.out.println(start);
    }

    static class Solution {
        static int canCompleteCircuit(int[] gas, int[] cost) {
            int length = gas.length;
            if (length != cost.length) return -1;
            int[] minus = new int[length];
            for (int i = 0; i < length; i++) minus[i] = gas[i] - cost[i];
            int start, end;
            for (start = 0; start < length; start++) {
                int remain = 0;
                for (end = start; Math.abs(end - start) <= length - 1; end++) {
                    remain += minus[end % length];
                    while (remain < 0) {
                        remain -= minus[start++];
                        if (start >= length) return -1;
                    }
                }
                if (Math.abs(end - start) > length - 1) break;
            }
            if (start >= length) return -1;
            return start;
        }
    }
}
